import java.awt.*;
import java.util.ArrayList;
import java.util.List;

/**
 * Created by jack on 18/3/25.
 */
public class Parentheses {
    List<String> ans = new ArrayList<String>();
    int n =0;
    public List<String> generateParentthesis(int n){
        this.n = n;
        backtrack("",0,0);
        return ans;
    }

    private void backtrack(String curr,int open ,int close){
        if(curr.length() == 2 * n){
            ans.add(curr);
            return ;
        }
        if(open < n){
            backtrack(curr + "(",open + 1, close);
        }
        if(close < open){
            backtrack(curr + ")",open,close+1);
        }
    }

    public static void main(String[] args) {
        Parentheses p = new Parentheses();
        List<String> stringList = p.generateParentthesis(3);
        for(String s : stringList){
            System.out.println(s);
        }

    }
}
